Owen Sullivan

Memory Allocator:
* DESCRIPTION: A shared library which re-implements malloc(), calloc(), free(), 
and realloc() using a BiBOP (Big Bag Of Pages)-style allocator and segregated 
free lists.
* KNOWN PROBLEMS:
** free() currently depends on calling malloc() to dynamically allocate memory 
for the next allocation in a free list, which can increase the runtime of the 
library by a theoretical maximum of 2x and increase the number of pages 
being allocated significantly. malloc() is implemented such that there is a 
chance that allocations available in the free list for a given allocation size 
are picked immediately, which should mean that no unnecessary pages are 
allocated for free list nodes, but a situation involving calls to malloc() with 
calls to free() immediately after will decrease the library's space-time 
efficiency.
* DESIGN:
** allocator.c, which compiles into libmyalloc.so, uses linked lists of pages 
of size 4096 bytes (or 4KB) where pages are split up based on allocation sizes 
in powers of 2.
** The BiBOP method is implemented using an array of pointers to the most-
recently allocated page of a given small allocation size, as opposed to using a 
linked list. Large pages are simply mapped and unmapped as needed without any 
connections between them.
** Each allocation has a distinct memory space, but is not tracked in any 
traditional sense. Rather, an array of pointers to the next unused allocation 
space for a given size works in conjunction with an array of free lists 
corresponding to the aforementioned size in order to determine where the next 
allocation should be.
** The malloc() re-implementation handles all pointer offsetting arithmatic, 
and malloc(), free(), and realloc() all make use of a bitwise mask to get 
the parent page of a given pointer for one reason or another.
** The calloc() re-implementation calls malloc(), but sets all memory returned 
by malloc() to initial values of 0.
** The free() re-implementation finds the parent page of the pointer being 
freed by its memory address, then determines whether the pointer being freed is 
a large chunk or a small allocation. If the pointer is a large chunk, the 
entire page is freed; if the pointer is a small allocation, the allocation is 
added to a free list so that it can be re-used.
** The realloc() re-implementation creates a new pointer (if necessary), 
copies memory data between the original and new pointers, then calls free() to 
free the old pointer.
** A helper function called getPageExponent() exists which calculates the 
exponent of the power of two provided as a parameter as fast as possible using 
__builtin_clz().
** A helper function called getAllocationSize() exists which calculates the 
closest-highest power of two of a given input.
* RESOURCES:
** After determining that a bitwise mask would be necessary to determine the 
parent page of a pointer passed to free() and/or realloc(), I encountered a 
problem with typecasting that (apparently) made my pointer arithmetic not 
equate to an integral expression. A bit of searching turned up a pointer type 
that can be used interchangeably with void pointers; Dr. Sorber actually 
explained this in class later, but here's the reference just in 
case: https://stackoverflow.com/a/1846648
** I found a fantastic reference for the fastest way to get the 
next-highest multiple of two of a given number, which helped me 
get rid of one more while loop for the sake of 
efficiency: https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2